package _interview75;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

/**
 * 215. 数组中的第K个最大元素
 */
public class No215 {
    /**
     * 1. 基于堆(优先队列)排序的选择方法
     */
    public int findKthLargest1(int[] nums, int k) {
        Queue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
        for (int num : nums) {
            heap.offer(num);
        }
        int ans = 0;
        for (int i = 0; i < k; i++) {
            ans = heap.poll();
        }
        return ans;
    }

    /**
     * 2. 基于快速排序的选择方法
     */
    public int findKthLargest2(int[] nums, int k) {
        int n = nums.length;
        sort(nums, 0, n - 1, k);
        return nums[k - 1];
    }

    private void sort(int[] arr, int start, int end, int k) {
        if (start >= end) return;
        int partition = partition(arr, start, end);
        if (k < partition + 1) sort(arr, start, partition, k);
        else if (k > partition + 1) sort(arr, partition + 1, end, k);
    }

    private int partition(int[] arr, int start, int end) {
        int standardNum = arr[start];
        int point = start;
        int temp;
        for (int i = start + 1; i <= end; i++) {
            if (arr[i] > standardNum) {
                point++;
                temp = arr[point];
                arr[point] = arr[i];
                arr[i] = temp;
            }
        }
        arr[start] = arr[point];
        arr[point] = standardNum;
        return point;
    }
}
